﻿#define _CRT_SECURE_NO_WARNINGS 1
/*
回文链表，实际上只是将回文数存储在链表中
解决办法1：        
// 时间复杂度O(n)
// 空间复杂度O(n)
//遍历链表，将数据存储到数组vector中，然后利用双指针，进行遍历查询。
解决办法2:
// 时间复杂度O(n)
// 空间复杂度O(1)
//利用快慢双指针找中间节点
//找到中间节点然后反转后半部分链表
//最后进行遍历确认即可
*/

//每日一题_05
//234. 回文链表
//https://leetcode.cn/problems/palindrome-linked-list/description/?fileGuid=xhPgrG6cGjpk6rVg

//解决办法1
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 时间复杂度O(n)
        // 空间复杂度O(n)
        vector<int> nums;
        while (head != nullptr) {
            nums.push_back(head->val);
            head = head->next;
        }

        // 下标模拟双指针
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            if (nums[left] == nums[right]) {
                left++;
                right--;
            }
            else {
                return false;
            }
        }
        return true;
    }
};

//解决办法2
class Solution {
public:
    // 快慢双指针找中间节点
    ListNode* Find_Mid_Node(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    // 反转链表
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        ListNode* n1 = nullptr;
        ListNode* n2 = head;
        ListNode* n3 = head->next;

        while (n2) {
            n2->next = n1;

            n1 = n2;
            n2 = n3;
            if (n3)
                n3 = n3->next;
        }

        return n1;
    }

    // 单链表
    bool isPalindrome(ListNode* head) {
        // 时间复杂度O(n)
        // 空间复杂度O(1)

        // 找寻中间节点
        ListNode* mid_node = Find_Mid_Node(head);

        // 反转后半部分链表
        ListNode* head2 = reverseList(mid_node);

        while (head2) {
            if (head->val != head2->val) {
                return false;
            }
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};